A number of applications on the Internet access structured data through keyword queries. Structured data may include data that is stored in a structured form (e.g., tuples) within repositories such as databases (relational, object, XML, etc.), delimited files, or other structured repositories. Structured data tuples often include attributes with each attribute taking on one of a set of possible attribute values. Typically, structured queries over structured data are evaluated in a strict fashion, i.e. the query-specified attributes and corresponding attribute values are matched exactly with the attributes and corresponding attributes of the structured data. Consider for example the following structured query submitted by a user to an online merchant:
{Brand:Sony, Color:Silver, Model:LCD, Size:42 inches}
In this structured query, the user is interested in finding silver-colored LCD televisions that are made by Sony and have a size of 42 inches. Although this structured query is relatively well-specified, if it is evaluated strictly very few or no results may be returned to the user. For example, there may be no silver-colored televisions that are 42 inches in size, or the only Sony LCD televisions may be 43 inches or other sizes other than 42 inches. Thus, it may be beneficial to “relax” the structured query provided by the user by changing one or more of the attribute values so that the user may receive a predetermined minimum number of results. However, determining which attribute values to relax is difficult because a user may become dissatisfied if returned results are too different than the original structured query, and there is only a finite amount of time during which relaxed attribute values may be considered before the user expects to receive results.